package main

import (
	"fmt"
)

/* 876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list/ */

func ExecQ876() {

	{
		node5 := &ListNode{Val: 5, Next: nil}
		node4 := &ListNode{Val: 4, Next: node5}
		node3 := &ListNode{Val: 3, Next: node4}
		node2 := &ListNode{Val: 2, Next: node3}
		node1 := &ListNode{Val: 1, Next: node2}

		fmt.Println(middleNode(node1))
	}

	{
		node6 := &ListNode{Val: 6, Next: nil}
		node5 := &ListNode{Val: 5, Next: node6}
		node4 := &ListNode{Val: 4, Next: node5}
		node3 := &ListNode{Val: 3, Next: node4}
		node2 := &ListNode{Val: 2, Next: node3}
		node1 := &ListNode{Val: 1, Next: node2}

		fmt.Println(middleNode(node1))
	}
}

// 我写的
func middleNode1(head *ListNode) *ListNode {
	vals := make([]*ListNode, 0, 100)
	getMiddleIndex := func() int {
		if size := len(vals); size < 2 {
			return size - 1
		} else {
			return size / 2
		}
	}
	vals = append(vals, head)
	next := head.Next
	midx := getMiddleIndex()
	nidx := 0
	node := vals[midx]
	for next != nil {
		vals = append(vals, next)
		midx = getMiddleIndex()
		if midx != nidx {
			nidx = midx
			node = vals[midx]
		}
		next = next.Next
	}
	return node
}

// 官方的 👍  快慢指针真的秀~~~
func middleNode(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}
